% LaTeX source for textbook ``How to think like a computer scientist''
% Copyright (c)  2001  Allen B. Downey, Jeffrey Elkner, and Chris Meyers.

% Permission is granted to copy, distribute and/or modify this
% document under the terms of the GNU Free Documentation License,
% Version 1.1  or any later version published by the Free Software
% Foundation; with the Invariant Sections being "Contributor List",
% with no Front-Cover Texts, and with no Back-Cover Texts. A copy of
% the license is included in the section entitled "GNU Free
% Documentation License".

% This distribution includes a file named fdl.tex that contains the text
% of the GNU Free Documentation License.  If it is missing, you can obtain
% it from www.gnu.org or by writing to the Free Software Foundation,
% Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
%

\chapter{Creating a new data type}
\label{overloading}
\index{data type!user-defined}

Object-oriented programming languages allow programmers to create new
data types that behave much like built-in data types.  We will explore
this capability by building a {\tt Fraction} class that works very much
like the built-in numeric types: integers, longs and floats.

Fractions, also known as rational numbers, are values that can be expressed
as a ratio of whole numbers, such as $5/6$. The top number is
called the numerator and the bottom number is called the denominator.

\index{rational}
\index{fraction}
\index{numerator}
\index{denominator}

We start by defining a {\tt Fraction} class with an initialization
method that provides the numerator and denominator as integers:

\adjustpage{-2}
\pagebreak

\beforeverb
\begin{verbatim}
class Fraction:
  def __init__(self, numerator, denominator=1):
    self.numerator = numerator
    self.denominator = denominator
\end{verbatim}
\afterverb
%
The denominator is optional.  A Fraction with just one
parameter represents a whole number.  If the numerator
is $n$, we build the Fraction
$n/1$.

The next step is to write a {\tt \_\_str\_\_} method that
displays fractions in a way that makes sense.  The form
``numerator/denominator'' is natural here:

\beforeverb
\begin{verbatim}
class Fraction:
  ...
  def __str__(self):
    return "%d/%d" % (self.numerator, self.denominator)
\end{verbatim}
\afterverb
%
To test what we have so far, we put it in a file named
{\tt Fraction.py} and import it into the Python interpreter.
Then we create a fraction object and print it.

\beforeverb
\begin{verbatim}
>>> from Fraction import Fraction
>>> spam = Fraction(5,6)
>>> print "The fraction is", spam
The fraction is 5/6
\end{verbatim}
\afterverb
%
As usual, the {\tt print} command invokes the {\tt \_\_str\_\_}
method implicitly.


\section {Fraction multiplication}
\index{multiplication!fraction}
\index{fraction!multiplication}

We would like to be able to apply the normal addition, subtraction,
multiplication, and division operations to fractions.  To do this, we
can overload the mathematical operators for {\tt Fraction} objects.

\index{overload}
\index{operator!overloading}
\index{mathematical operator}

We'll start with multiplication because it is the easiest to implement.
To multiply fractions, we create a new fraction with a numerator
that is the product of the original numerators and a denominator that
is a product of the original denominators.  {\tt \_\_mul\_\_} is the
name Python uses for a method that overloads the {\tt *} operator:

\beforeverb
\begin{verbatim}
class Fraction:
  ...
  def __mul__(self, other):
    return Fraction(self.numerator*other.numerator,
                    self.denominator*other.denominator)
\end{verbatim}
\afterverb
%
We can test this method by computing the product of two fractions:

\beforeverb
\begin{verbatim}
>>> print Fraction(5,6) * Fraction(3,4)
15/24
\end{verbatim}
\afterverb
%
It works, but we can do better!  We can extend the method to
handle multiplication by an integer.  We use the {\tt isinstance} function
to test if {\tt other} is an integer and convert it to a fraction if
it is.

\beforeverb
\begin{verbatim}
class Fraction:
  ...
  def __mul__(self, other):
    if isinstance(other, int):
      other = Fraction(other)
    return Fraction(self.numerator   * other.numerator,
                    self.denominator * other.denominator)
\end{verbatim}
\afterverb
%
Multiplying fractions and integers now works, but only if the fraction
is the left operand:

\beforeverb
\begin{verbatim}
>>> print Fraction(5,6) * 4
20/6
>>> print 4 * Fraction(5,6)
TypeError: __mul__ nor __rmul__ defined for these operands
\end{verbatim}
\afterverb
%
To evaluate a binary operator like multiplication, Python checks
the left operand first to see if it provides a {\tt \_\_mul\_\_}
that supports the type of the second operand.  In this case,
the built-in integer operator doesn't support fractions.

Next, Python checks the right operand to see if it provides
an {\tt \_\_rmul\_\_} method that supports the first type.  In
this case, we haven't provided {\tt \_\_rmul\_\_}, so it fails.

On the other hand, there is a simple way to provide
{\tt \_\_rmul\_\_}:

\beforeverb
\begin{verbatim}
class Fraction:
  ...
  __rmul__ = __mul__
\end{verbatim}
\afterverb
%
This assignment says that the {\tt \_\_rmul\_\_} is the same
as {\tt \_\_mul\_\_}.
Now if we evaluate {\tt 4 * Fraction(5,6)}, Python invokes
{\tt \_\_rmul\_\_} on the {\tt Fraction} object and passes 4
as a parameter:

\beforeverb
\begin{verbatim}
>>> print 4 * Fraction(5,6)
20/6
\end{verbatim}
\afterverb
%
Since {\tt \_\_rmul\_\_} is the same as {\tt \_\_mul\_\_}, and
{\tt \_\_mul\_\_} can handle an integer parameter, we're all set.


\section{Fraction addition}
\index{addition!fraction}
\index{fraction!addition}

Addition is more complicated than multiplication, but still not too
bad.  The sum of $a/b$ and $c/d$ is the fraction
{\tt (a*d+c*b)/(b*d)}.

Using the multiplication code as a model, we can write
{\tt \_\_add\_\_} and {\tt \_\_radd\_\_}:

\beforeverb
\begin{verbatim}
class Fraction:
  ...
  def __add__(self, other):
    if isinstance(other, int):
      other = Fraction(other)
    return Fraction(self.numerator   * other.denominator +
                    self.denominator * other.numerator,
                    self.denominator * other.denominator)

  __radd__ = __add__
\end{verbatim}
\afterverb
%
We can test these methods with {\tt Fraction}s and integers.

\beforeverb
\begin{verbatim}
>>> print Fraction(5,6) + Fraction(5,6)
60/36
>>> print Fraction(5,6) + 3
23/6
>>> print 2 + Fraction(5,6)
17/6
\end{verbatim}
\afterverb
%
The first two examples invoke {\tt \_\_add\_\_}; the last
invokes {\tt \_\_radd\_\_}.


\section{Euclid's algorithm}
\index{greatest common divisor}
\index{Euclid}
\index{pseudocode}
\index{reduce}

In the previous example, we computed the sum $5/6 + 5/6$ and got
$60/36$.  That is correct, but it's not the best way to represent the
answer.  To {\bf reduce} the fraction to its simplest terms, we have
to divide the numerator and denominator by their {\bf greatest common
divisor (GCD)}, which is 12.  The result is $5/3$.

In general, whenever we create a new {\tt Fraction} object, we should
reduce it by dividing the numerator and denominator by their GCD.  If
the fraction is already reduced, the GCD is 1.

Euclid of Alexandria (approx. 325--265 BCE) presented an algorithm
to find the GCD for two integers $m$ and $n$:

\begin{quote}
If $n$ divides $m$ evenly, then $n$ is the GCD.  Otherwise
the GCD is the GCD of $n$ and the remainder of $m$ divided by $n$.
\end{quote}

This recursive definition can be expressed concisely as a function:

\beforeverb
\begin{verbatim}
def gcd (m, n):
  if m % n == 0:
    return n
  else:
    return gcd(n, m%n)
\end{verbatim}
\afterverb
%
In the first line of the body, we use the modulus operator to
check divisibility.  On the last line, we use it to compute
the remainder after division.

Since all the operations we've written
create new {\tt Fraction}s for the result, we can reduce all results
by modifying the initialization method.

\beforeverb
\begin{verbatim}
class Fraction:
  def __init__(self, numerator, denominator=1):
    g = gcd (numerator, denominator)
    self.numerator   =   numerator / g
    self.denominator = denominator / g
\end{verbatim}
\afterverb
%
Now whenever we create a {\tt Fraction}, it is reduced to its simplest
form:

\beforeverb
\begin{verbatim}
>>> Fraction(100,-36)
-25/9
\end{verbatim}
\afterverb
%
A nice feature of {\tt gcd} is that if the fraction is
negative, the minus sign is always moved to the numerator.


\section{Comparing fractions}
\index{comparison!fraction}
\index{fraction!comparison}

Suppose we have two {\tt Fraction} objects, {\tt a} and {\tt b}, and we
evaluate {\tt a == b}.  The default implementation of {\tt ==}
tests for shallow equality, so it only returns true if {\tt a}
and {\tt b} are the same object.

More likely, we want to return true if $a$ and $b$ have
the same value---that is, deep equality.

We have to teach fractions how to compare themselves.  As we saw in
Section~\ref{comparecard}, we can overload all the comparison
operators at once by supplying a {\tt \_\_cmp\_\_} method.

By convention, the {\tt \_\_cmp\_\_} method returns a
negative number if {\tt self} is less than {\tt other}, zero
if they are the same, and a positive number if {\tt self} is greater
than {\tt other}.

The simplest way to compare fractions is to cross-multiply.
If $a/b > c/d$, then $ad > bc$.
With that in mind, here is the code for {\tt \_\_cmp\_\_}:

\beforeverb
\begin{verbatim}
class Fraction:
  ...
  def __cmp__(self, other):
    diff = (self.numerator  * other.denominator -
            other.numerator * self.denominator)
    return diff
\end{verbatim}
\afterverb
%
If {\tt self} is greater than {\tt other}, then {\tt diff}
will be positive.  If {\tt other} is greater, then {\tt diff}
will be negative.  If they are the same, {\tt diff} is zero.


\section {Taking it further}

Of course, we are not done.  We still have to implement
subtraction by overriding {\tt \_\_sub\_\_} and division
by overriding {\tt \_\_div\_\_}.

One way to handle those operations is to implement negation
by overriding
{\tt \_\_neg\_\_} and inversion by overriding {\tt \_\_invert\_\_}.
Then we can subtract by negating the second operand and adding,
and we can divide by inverting the second operand and
multiplying.

Next, we have to provide {\tt \_\_rsub\_\_} and {\tt \_\_rdiv\_\_}.
Unfortunately, we can't use the same trick we used for addition and
multiplication, because subtraction and division are not commutative.
We can't just set {\tt \_\_rsub\_\_} and {\tt \_\_rdiv\_\_} equal to
{\tt \_\_sub\_\_} and {\tt \_\_div\_\_}.  In these operations, the
order of the operands makes a difference.

To handle {\bf unary negation}, which is the use of the minus
sign with a single operand, we override {\tt \_\_neg\_\_}.

\index{unary operator}
\index{negation}

We can compute powers by overriding {\tt \_\_pow\_\_},
but the implementation is a little tricky.  If the exponent isn't
an integer, then it may not be possible to represent the result
as a {\tt Fraction}.  For example, {\tt Fraction(2) ** Fraction(1,2)}
is the square root of 2, which is an irrational number (it can't
be represented as a fraction).
So it's not easy to write the most general version of {\tt \_\_pow\_\_}.

\index{irrational}

There is one other extension to the {\tt Fraction} class that you might
want to think about.  So far, we have assumed that the numerator
and denominator are integers.

\begin{quote}
{\em As an exercise, finish the implementation of the {\tt Fraction}
class so that it handles subtraction, division and exponentiation.}
\end{quote}



\section{Glossary}

\begin{description}

\item[greatest common divisor (GCD):] The largest positive integer
that divides without a remainder into both the numerator and denominator
of a fraction.

\item[reduce:] To change a fraction into an equivalent form with a
GCD of 1.

\item[unary negation:] The operation that computes an additive
inverse, usually denoted with a leading minus sign.  Called 
``unary'' by contrast with the binary minus operation, which is
subtraction.


\index{greatest common divisor}
\index{reduce}
\index{unary negation}

\end{description}
